#ifndef _csLinkList_h_
#define _csLinkList_h_

/********************************************************************
	created:	2009/11/11
	created:	11:11:2009   15:44
	filename: 	e:\CrazySprite\code\src\cscorelib\csLinkList.h
	file path:	e:\CrazySprite\code\src\cscorelib
	file base:	csLinkList
	file ext:	h
	author:		dongchengok
	
	purpose:	normal link list, use new to alloc memory, must be 
				construct/destruct object
*********************************************************************/
template<typename T>
class csLinkList
{
public:
	struct Node
	{
		csINLINE Node(){}
		csINLINE Node(const Node& node):m_data(node.m_data),m_prev(node.m_prev),m_next(node.m_next){}
		csINLINE Node(const T& val):m_data(val){}
		T					m_data;
		Node*				m_prev;
		Node*				m_next;
	};
	class iterator
	{
		friend class csLinkList;
	public:
		csINLINE iterator(){}
		csINLINE iterator(const iterator& it):m_node(it.m_node){}
		csINLINE iterator(Node* node):m_node(node){}
		csINLINE bool		operator==(const iterator& rhs) const{return m_node==rhs.m_node;}
		csINLINE bool		operator!=(const iterator& rhs) const{return m_node!=rhs.m_node;}
		csINLINE iterator&	operator++(){csASSERT(m_node);m_node=m_node->m_next;return *this;}
		csINLINE iterator	operator++(s32){csASSERT(m_node);m_node=m_node->m_next;return iterator(m_node->m_prev);}
		csINLINE iterator&	operator--(){csASSERT(m_node);m_node=m_node->m_prev;return *this;}
		csINLINE iterator	operator--(s32){csASSERT(m_node);m_node=m_node->m_prev;return iterator(m_node->m_next);}
		csINLINE T&			operator *(){csASSERT(m_node);return m_node->m_data;}
		csINLINE T*			operator->(){csASSERT(m_node);return &(m_node->m_data);}
		csINLINE void		next(){csASSERT(m_node);m_node=m_node->m_next;}
		csINLINE void		prev(){csASSERT(m_node);m_node=m_node->m_prev;}
	protected:
		Node*				m_node;
	};
	class const_iterator
	{
		friend class csLinkList;
	public:
		csINLINE const_iterator(){}
		csINLINE const_iterator(const const_iterator& it):m_node(it.m_node){}
		csINLINE const_iterator(const Node* node):m_node(node){}
		csINLINE bool				operator==(const const_iterator& rhs) const{return m_node==rhs.m_node;}
		csINLINE bool				operator!=(const const_iterator& rhs) const{return m_node!=rhs.m_node;}
		csINLINE const_iterator&	operator++(){csASSERT(m_node);m_node=m_node->m_next;return *this;}
		csINLINE const_iterator		operator++(s32){csASSERT(m_node);m_node=m_node->m_next;return const_iterator(m_node->m_prev);}
		csINLINE const_iterator&	operator--(){csASSERT(m_node);m_node=m_node->m_prev;return *this;}
		csINLINE const_iterator		operator--(s32){csASSERT(m_node);m_node=m_node->m_prev;return const_iterator(m_node->m_next);}
		csINLINE const T&			operator *(){csASSERT(m_node);return m_node->m_data;}
		csINLINE const T*			operator->(){csASSERT(m_node);return &(m_node->m_data);}
		csINLINE void				next(){csASSERT(m_node);m_node=m_node->m_next;}
		csINLINE void				prev(){csASSERT(m_node);m_node=m_node->m_prev;}
	protected:
		const Node*					m_node;
	};
	class reverse_iterator
	{
		friend class csLinkList;
	public:
		csINLINE reverse_iterator(){}
		csINLINE reverse_iterator(const reverse_iterator& it):m_node(it.m_node){}
		csINLINE reverse_iterator(Node* node):m_node(node){}
		csINLINE bool				operator==(const reverse_iterator& rhs) const{return m_node==rhs.m_node;}
		csINLINE bool				operator!=(const reverse_iterator& rhs) const{return m_node!=rhs.m_node;}
		csINLINE reverse_iterator&	operator++(){csASSERT(m_node);m_node=m_node->m_prev;return *this;}
		csINLINE reverse_iterator	operator++(s32){csASSERT(m_node);m_node=m_node->m_prev;return reverse_iterator(m_node->m_next);}
		csINLINE reverse_iterator&	operator--(){csASSERT(m_node);m_node=m_node->m_next;return *this;}
		csINLINE reverse_iterator	operator--(s32){csASSERT(m_node);m_node=m_node->m_next;return reverse_iterator(m_node->m_prev);}
		csINLINE T&					operator *(){csASSERT(m_node);return m_node->m_data;}
		csINLINE T*					operator->(){csASSERT(m_node);return &(m_node->m_data);}
		csINLINE void				next(){csASSERT(m_node);m_node=m_node->m_prev;}
		csINLINE void				prev(){csASSERT(m_node);m_node=m_node->m_next;}
	protected:
		Node*						m_node;
	};
	class const_reverse_iterator
	{
		friend class csLinkList;
	public:
		csINLINE const_reverse_iterator(){}
		csINLINE const_reverse_iterator(const const_reverse_iterator& it):m_node(it.m_node){}
		csINLINE const_reverse_iterator(const Node* node):m_node(node){}
		csINLINE bool						operator==(const const_reverse_iterator& rhs) const{return m_node==rhs.m_node;}
		csINLINE bool						operator!=(const const_reverse_iterator& rhs) const{return m_node!=rhs.m_node;}
		csINLINE const_reverse_iterator&	operator++(){csASSERT(m_node);m_node=m_node->m_prev;return *this;}
		csINLINE const_reverse_iterator		operator++(s32){csASSERT(m_node);m_node=m_node->m_prev;return const_reverse_iterator(m_node->m_next);}
		csINLINE const_reverse_iterator&	operator--(){csASSERT(m_node);m_node=m_node->m_next;return *this;}
		csINLINE const_reverse_iterator		operator--(s32){csASSERT(m_node);m_node=m_node->m_next;return const_reverse_iterator(m_node->m_prev);}
		csINLINE const T&					operator *() const{csASSERT(m_node);return m_node->m_data;}
		csINLINE const T*					operator->() const{csASSERT(m_node);return &(m_node->m_data);}
		csINLINE void						next(){csASSERT(m_node);m_node=m_node->m_prev;}
		csINLINE void						prev(){csASSERT(m_node);m_node=m_node->m_next;}
	protected:
		const Node*							m_node;
	};
public:
	csLinkList();
	csLinkList(const csLinkList<T>& list);
	~csLinkList();

	void					operator =(const csLinkList<T>& list);
	bool					operator==(const csLinkList<T>& rhs) const;
	bool					operator!=(const csLinkList<T>& rhs) const;

	T&						front();
	const T&				front() const;
	T&						back();
	const T&				back() const;

	void					push_back(const T& val);
	void					pop_back();
	void					push_front(const T& val);
	void					pop_front();

	iterator				begin();
	const_iterator			begin() const;
	iterator				end();
	const_iterator			end() const;
	reverse_iterator		rbegin();
	const_reverse_iterator	rbegin() const;
	reverse_iterator		rend();
	const_reverse_iterator	rend() const;

	iterator				insert(iterator where, const T& val);
	void					remove(iterator where);
	iterator				remove_return_next(iterator where);		//custom function
	void					remove(const T& val);

	iterator				find(const T& val);						//custom function
	const_iterator			find(const T& val) const;				//custom function
	iterator				find(const T& val, iterator it);						//custom function
	const_iterator			find(const T& val, const_iterator it) const;				//custom function
	bool					empty() const;
	s32						size() const;
	void					clear();
	void					swap(csLinkList<T>& rhs);
	void					to_array(T** outArray) const;

protected:
	void					_assign(const_iterator frontNode, const_iterator backNode);
	
protected:
	Node*					m_head;
	s32						m_size;
};
#include "csLinkList.inl"
#endif // _csLinkList_h_